
const NIL = {
  key = undefined,
  color = 0,
  lChild = null,
  rChild = null,
}

// 0: 红色   1： 黑色   2：双重黑
class Node {
  constructor(key, color = 0, lChild = NIL, rChild = NIL) {
    this.key = key;
    this.color = color;
    this.lChild = lChild;
    this.rChild = rChild;
  }
}

function getNewRoot(key) {
  return new Node(key);
}
function hasRedChild(root) {
  return root.lChild.color === 0 || root.rChild.color === 0;
}

// root, key, return newRoot
Node.prototype._insert = function (root, key) {
  if(root === NIL) return getNewRoot(key);
  if(root.key === key) return root;
  if(key > root.key) {
    root.rChild = this._insert(root.rChild, key);
  } else {
    root.lChild = this._insert(root.lChild, key);
  }

  return this.insert_maintrain(root)
}

Node.prototype.insert = function (root, key) {
  root = this._insert(root,key);
  root.color = 0;
  return root;
} 

// 调整root, return newRoot

// root: 祖父节点
Node.prototype.insert_maintrain = function(root) {
  let flag = 0; // 0: 未失衡 1： L失衡  2： R失衡

  if(root.lChild.color === 0 && hasRedChild(root.lChild)) flag = 1; // L
  if(root.rChild.color === 0 && hasRedChild(root.rChild)) flag = 2; // R
  if(flag === 0) return root;

  // 情况一：父 + 叔 都是红色
  if(root.lChild.color === 0 && root.rChild.color === 0) {
    root.color = 0;
    root.lChild.color = root.rChild.color = 1;
  }

  // 情况二： 叔为黑  LL LR RR RL
  if(flag === 1) { // L
    if(root.lChild.rChild.color === 0) { // LR
      root.lChild = left_roate(root.lChild);
    }
    // LL 
    root = right_rotate(root);
  } else { // R
    if(root.rChild.lChild.color === 0) { //RL
      root.rChild = right_rotate(root.rChild)
    }
    // RR 
    root = left_roate(root);
  }

  // 红色上浮
  root.color = 0;
  root.lChild.color = root.rChild.color = 1;

  return root;
}
